package leetcode_题库;

import java.util.Arrays;

/**
 * Created by IntelliJ IDEA.
 *
 * @Author : Ding
 * @create 2022/8/19 17:31
 */
public class _88_合并两个有序数组 {
    public static void main(String[] args) {
        int[] nums1 = new int[]{1,2,3,0,0,0};
        int m = 3;
        int[] nums2 = new int[]{2,5,6};
        int n = 3;

//        addTwoArrays(nums1,m,nums2,n);
        addTwoArrays2(nums1,m,nums2,n);

        System.err.println(Arrays.toString(nums1));
    }

    private static void addTwoArrays2(int[] nums1, int m, int[] nums2, int n) {
        /*
            排序算法，先进行复制，然后进行追加
            可以看出，这种算法非常简单，但是效率很差
         */
        System.arraycopy(nums2,0,nums1,m,n);
        Arrays.sort(nums1);
        /*
            > 2022/08/19 18:26:49
            解答成功:
                执行耗时:1 ms,击败了26.64% 的Java用户
                内存消耗:41.8 MB,击败了5.08% 的Java用户
         */
    }

    private static void addTwoArrays(int[] nums1, int m, int[] nums2, int n) {
        /*
            【mine】
            因为两个数组都是非递减排序，因此可以定义双指针，指定在每个数组的“右边界”，
            对于nums1来说，是有效右边界，如例子中的“3”
         */
        //让指针1在nums1的右边界
        int p1 = m - 1;
        //让指针2早nums2的右边界
        int p2 = n - 1;

        if (p2 == -1){
            //如果p2没有元素，直接就是nums1，返回即可
            return;
        }

        if (p1 == -1){
            //如果nums1没有元素，直接使用最优的赋值函数，将数组nums2复制给nums1即可
            System.arraycopy(nums2,0,nums1,0,n);
            return;
        }

        //此时，nums1和nums2都有元素，若如此，则循环持续
        while (p1 >= 0 && p2 >= 0){
            if (nums1[p1] > nums2[p2]){
                //若指针1所在元素大，就让指针1的值赋给两指针角标+1处（因为数组角标比长度-1，所以合并时，需要加回来一个）
                nums1[p1+p2 + 1] = nums1[p1];
                //指针1左移
                p1 --;
            }else{
                //若指针2所在元素大，就让指针2的值赋给两指针角标+1处
                nums1[p1+p2 + 1] = nums2[p2];
                //指针2左移
                p2 --;
            }
        }
        //此时，如果p2还没有走到尽头，那么合并未结束，但是p1后面的都已有序，直接把p2剩下的元素赋给p1即可
//        while (p2 >= 0){
//            nums1[p2] = nums2[p2--];
//        }
        //所以当然可以用性能更好的System.arraycopy
        if (p2 >= 0){
            System.arraycopy(nums2,0,nums1,0,p2+1);
        }

        /*
            > 2022/08/19 18:27:03
            解答成功:
                执行耗时:0 ms,击败了100.00% 的Java用户
                内存消耗:41 MB,击败了96.49% 的Java用户
         */
    }
}
